Synchronous time division multiplexing (STDM) is commonly used in the prior art in order to increase line utilization and efficiency in communications between the remote terminals and the central processor in time sharing data processing systems. In synchronous time division multiplexing, fixed time slots are assigned to each terminal, regardless of whether the particular terminal has a message to transmit or not. After one user's time interval has elapsed, the common communication line or channel between the individual terminals and the central processor is assigned to another user.
Since most terminals use only five percent of the total time, and are idle ninety-five percent of the total time, it is clear that the prior art synchronous time division multiplexing is inefficient insofar as the optimization of channel use is concerned. A more flexible and efficient system, namely asynchronous time division multiplexing (ATDM) has been introduced, which allocates a time slot in a common communication channel only when a terminal has a message to transmit. Unused channel bandwidth is available to support extra terminals. Since the multiplexed messages transmitted over the communication channel in the ATDM system are in a random order, such multiplexing is also known as statistical multiplexing. A somewhat similar multiplexing system has been used in voice communication. An operating example is the "Time Assignment Speech Interpolation" (TASI) system used by the Bell System on the Atlantic Ocean cable. Using the TASI system, the efficiency of transmission capacity has been doubled with negligible degradation in performance.
There are, however, two main differences in designing a statistical multiplexing system for voice and for computer data. In voice communication, there are many redundancies in speech; therefore, certain amounts of errors in speech can be tolerated without impairing the capability of the system to convey the entire conversation. However, in order to preserve the natural voice quality in the voice communication system, a real time requirement is important; that is, the voice signal should be presented in a continuous stream of information. In the data communication case, on the other hand, almost the opposite situation occurs. Usually there is no redundant data in data communications, but the reliability of the data is extremely important. However, message delays are not as critical in data communications as in voice communications, and variations in delays from one message to another are tolerable so long as the maximum message response delay is within a certain limit. Thus the approaches of designing the multiplexing system for these two types of systems are quite different.
In the speech case, because of the real time requirements, buffering is used for speech interpolation; and therefore, is only limited to one frame. Because of the real time requirements, no buffering can be used to store peak load traffic in the voice systems. As soon as the input is greater than the output communication channel bandwidth, the system immediately overflows and certain speech signals are lost. Since there are many redundancies in the speech conversations, as long as the loss is not too high, the speech quality can still be acceptable. In the data communication case, however, a much higher level of data accuracy is required, therefore, whenever the data communication system overflows, no data should be lost. Furthermore, computer traffic arrives in burst form, which implies that if there is an overflow, it could be an overflow of a large amount of data. To prevent such a loss, a large data buffer is required in the data communication system to temporarily store and handle the peak input traffic load. Input traffic rejection control mechanisms are also needed in the data communication system to prevent buffer overflow. Since the users response delay in the data communication system is less critical than in the voice communication system, data characters from the same source (terminal) may be grouped together and form a sub-block in order to save address overhead. Time out control mechanisms are required in the data communication system to prevent excessive response delays. Thus the statistical multiplexing systems for speech and data are quite different, in spite of the fact both systems try to efficiently utilize the idle periods in the communication channel.
Statistical multiplexing for computer communications involves a certain amount of complexity because every message transmitted over the common communication line must be accompanied by an address which identifies the terminal from which it originated, and because buffering is required to handle the random message arrivals at statistical peaks. To avoid buffer overflow, selectively input rejections are required when the buffer reach a certain maximum size or when a certain terminal has excess input traffic which could cause buffer overflow. Since most of the terminals use only five percent of the total time in the transmission of data to the central processor, only thirty percent of the total time in the reception of data from the central processor, with careful design, the performance improvements of statistical multiplexing systems over the synchronous time division multiplexing (STDM) system can be as high as three hundred to four hundred percent. In other words, for the same communication channel, up to three to four times the number of terminals can be supported in the statistical multiplexing system as compared with the conventional STDM system. The present invention is concerned with an implementation of the statistical multiplexing system for computer communications.
The statistical multiplexing system of the present invention consists of two integral parts: a multiplexer and a demultiplexer. In the multiplexer, messages received from the various terminals are labelled by addresses and are statistically multiplexed for transmission over a common communication channel to central processors or other remote systems. A multiplicity of the terminals are connected to the multiplexer, in which the received messages from the individual terminals are multiplexed on statistical multiplexing basis for transmission over the common channels to the remote central processors or multiplexers.
Each terminal is connected to the multiplexer through a separate interface circuit. Each message, or character, from the individual terminals is parity checked in its interface circuit and fed to the multiplexer. All characters received correctly from the individual terminals are echoed back to the users. If a character is not correctly received, as detected by a parity bit error, that character is not echoed back, and the user is made aware that the character must be retyped. It is to be noted that the foregoing is a local echo feature, which is different from the remote echo technique used by most of the prior art existing systems.
In the system of the invention, and unlike the prior art synchronous time division multiplexing system, time slots are assigned to each character received by the multiplexer, but no time slots are assigned for the idle terminals, and this greatly increases the channel utilization in the common output communication line. To handle traffic at the statistical peaks, a two-stage buffer memory is included in the multiplexer. In the first embodiment of the invention to be described, the first stage of the buffer consists of a first-in-first-out (FIFO) memory, and the second stage consists of a read/write (R/W) memory.
The FIFO serves to collect the randomly received characters from all the input terminals, each character including a start bit, a stop bit, and a parity bit. These bits are removed before the characters are fed into the FIFO, and the address label is added to each character, which identifies the terminal from which it was received. The contents of the FIFO are then fed to the second stage of the buffer memory, which is the R/W memory, in which they are formed into a data block for transmission. To improve line efficiency, several characters from the same terminal can be collected together in the R/W memory to form a sub-block, with all the characters being identified by a single address label, which reduces the address label requirements in the data structure. A microprocessor is included in the multiplexing system for such message handling.
The multiplexer also includes a block time-out circuit which serves to notify the microprocessor when a prescribed block time-out interval has elasped since a first character was received by the R/W memory to form a sub-block. When a block time-out circuit causes all the sub-blocks which contain at least one data character to be chained together to form a data block. The resulting data block is transferred to a synchronous transmitter via a direct memory access (DMA) facility for transmission to the remote central processor or remote multiplexer over the common communication channel. The block time-out circuit prevents excessive response time delays. Should a data block be filled up to its maximum length before the time-out interval established by the block time-out circuit, that data block is immediately transmitted over the common communication channel to the remote central processor or multiplexer.
The DMA facility is an important feature in the present invention in that it provides direct transfer of data from the R/W memory to the synchronous transmitter without involving the microprocessor operation. The DMA not only provides a much higher data transfer rate but also greatly reduces the microprocessor load and thus significantly increases the throughput of the multiplexing system. The DMA operation is initiated by the microprocessor and terminates by the byte count of the block size that was loaded in the DMA facility.
The demultiplexer is also provided in the statistical multiplexing system of the invention, as mentioned above. The demultiplexer is coupled to individual terminals, so that messages for the individual terminals received from the central processor over the common communication channel in a statistical multiplexed format may be demultiplexed and directed to the terminals identified by the individual data sub-blocks.
The demultiplexer performs a zero delete (deletes the zero after five consecutive one's which was inserted by the synchronous transmitter), initiates the transfer of data from the synchronous receiver to the R/W memory via the DMA facility, performs error checking, and sets a status register. The microprocessor in response to the status of the status register, issues the appropriate acknowledgment message to the sender. The microprocessor then performs the necessary memory management functions; for example, it chains all the received data sub-blocks for the same terminal in the proper order and distributes the data sub-blocks to its corresponding terminal.
Continuous error detection and retransmission techniques are used in the system of the invention for error control. The system continuously transmits data blocks to the central processor or other remote location without waiting for the acknowledgment of the previously transmitted data blocks. The system holds on all the transmitted data blocks in the R/W memory, and the buffer space of a transmitted data block is released from the R/W memory only when the system receives a positive acknowledgment of that data block from the remote location. Incorrectly received data blocks are retransmitted by the system.
In addition to using positive acknowledgment to indicate correctly received data blocks from the remote location, a unique feature is incorporated into the system of the invention which involves sending negative acknowledgments to the remote location for incorrectly received data blocks. With negative acknowledgments, The system at the remote location is able to detect an error data block much faster than waiting for the acknowledgment time-out circuit to operate. Thus, the negative acknowledgment feature in the system of the invention improves the throughput and buffer utilization of the system. In the system of the invention, acknowledgment time-out is used for abnormal errors, for example, if a negative acknowledgment is lost during transmission.
This invention also included an alternative implementation of the first buffer memory of the statistical multiplexing system. Instead of using a centralized first buffer memory, a separate microcomputer providing a first buffer memory may be provided in each terminal interface circuit. Data sub-blocks from the same terminal may now be formed in each terminal interface circuit. Providing a first buffer memory at each terminal interface circuit greatly reduces the processing load of the multiplexer microprocessor for forming the data sub-blocks and thus provides a higher system throughput. The present-day availability of low cost microcomputers on LSI chips permits economical implementation of the aforesaid approach of using a microcomputer for each terminal interface.
in the alternative implementation, a scanner periodically initiates the transfer of the full or partially full sub-blocks with address and sub-block size count from the interface circuits to the second buffer memory (R/W memory) via the direct memory access (DMA) circuit. In the exact same manner as described previously, the microprocessor then collects all the received sub-blocks and multiplexes them into data blocks for transmission over the common communication channel to the remote locations.
In the demultiplexer of the alternative implementation, the buffer system consists of a dedicated buffer for each terminal and a shared buffer for storing data blocks when a dedicated individual buffer overflows. The microprocessor uses a unique technique to dynamically manage the received statistical multiplexed data blocks from the communication channel and to transfer the received data sub-blocks from the second buffer memory to the first buffer memories in the terminal interface circuits by way of the DMA circuit.
To protect data integrity and to prevent buffer overflow in the alternative implementation, traffic control mechanisms are incorporated with the aid of buffer occupancy status registers. With microprocessor control the system is capable of rejecting input traffic when the second buffer memory reaches a certain maximum size, or when certain terminals exceed their prescribed input traffic rate.
A further implementation of statistical multiplexing data block structure which reduces the address overhead at heavy traffic load will also be described. Such data block structure includes an address information table which consists of sub-block indicator bits and sub-block size count bits for each terminal. The data field of a frame of data block consists of the address information table, and sub-blocks (without address label) collected from a complete scan of all the asynchronous input terminals. The sub-blocks are multiplexed in a fixed sequence order. If a terminal does not have any data to transmit during a scanning period, no sub-blocks are assigned for that terminal and the indicator bit for that terminal is set to zero. Such data structure is more restrictive (for example, priority scanning cannot be permitted), and more complex in data handling, than the data structure which consists of address labels. However, it does provide a reudction of about fifty percent in address overhead for heavy traffic loads.
Another important feature of the statistical multiplexing system of the present invention is that it not only can process messages to and from a plurality of asynchronous terminals but it is also capable of processing messages to and from a plurality of high speed synchronous terminals. To accomplish this, a synchronous terminal interface circuit is required to handle synchronous input data. In the same manner as the asynchronous terminals, the scanner periodically transfers data sub-block from the first buffer memory of the synchronous terminal interface circuit to the second buffer memory by way of the DMA circuit. The traffic arrival pattern of the synchronous terminals is different from that of the asynchronous terminals. The traffic arrives from the synchronous terminals usually as a continuous stream of data characters rather than as a random single character. As a result, the data sub-blocks collected in the first buffer memory of the synchronous terminal circuit interface are much larger than the sub-blocks from the asynchronous terminal interface circuits. Therefore, the sub-blocks from the synchronous terminals can be viewed as multiplexed data blocks from the plural asynchronous terminals. The multiplexer microprocessor schedules and multiplexes the sub-blocks from the synchronous terminals and the data blocks from the asynchronous terminals over the common communication channel to the remote location.